package com.zdp.leetcodeMiddle;

/*
* 题目描述：
* 给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最长回文子串_5 {

    /*
    * 关于回文串，可以联想到Manacher算法
    * */
    public String longestPalindrome(String s) {
        return manacher(s);
    }

    // 处理字符串，加入特殊字符
    public  char[] manacherString(String str){
        char[] arr = str.toCharArray();
        char[] res = new char[str.length()*2 +1];
        // 加入特殊字符
        int index = 0;
        for(int i=0;i < arr.length;i++){
            res[index++] = '#';
            res[index++] = arr[i];
        }
        res[index] = '#';
        return res;
    }

    // manacher 算法
    public  String manacher(String str){
        char[] arr = manacherString(str);
        // 回文半径数组
        int[] radius = new int[arr.length];
        // 回文右边界
        int pr = 0;
        // 回文右边界中心点
        int center = 0;
        // 最长的那个
        int maxLength = Integer.MIN_VALUE;
        int maxIndex = 0;
        // 开始计算
        for(int i=0;i<arr.length;i++){
            // 判断是否在回文右边界内部
            radius[i] = pr>i?Math.min(radius[center*2-i],pr-i-1):0;
            // 无论是否在回文右边界内部，都进行一次扩充
            // 边界条件
            while(i+radius[i]+1 < arr.length && i-radius[i]-1 >-1){
                if(arr[i+radius[i]+1] == arr[i-radius[i]-1]){
                    radius[i]++;
                }else{
                    // 不符合就退出
                    break;
                }
            }
            // 更新最右边界和中心点
            if(i+radius[i]>pr){
                pr = i+radius[i];
                center = i;
            }
            if(maxLength<radius[i]){
                maxLength = radius[i];
                maxIndex = i;
            }
        }
        // 转换为字符串
        int i = maxIndex-maxLength;
        char[] res = new char[maxLength*2 +1];
        int index = 0;
        while(i<=maxIndex+maxLength){
            res[index++] = arr[i++];
        }
        String s = String.valueOf(res);
        s= s.replace("#","");
        return s;
    }


}
